#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Node {
   public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
   public:
    bool findOther(vector<int>& nums, int start, int end, int target) {
        //使用二分查找
        while (start < end) {
            int mid = (start + end) / 2;
            if (nums[mid] == target || nums[start] == target ||
                nums[end] == target) {
                return true;
            }
            if (nums[mid] < target) {
                //去右边找
                if (end - start == 1) {
                    return false;
                }
                start = mid;
            } else {
                //去左边找
                end = mid;
            }
        }
        return false;
    }
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        //滑动窗口解决
        for (int i = 0; i < nums.size() - 1; i++) {
            if (findOther(nums, i + 1, nums.size() - 1, target - nums[i])) {
                ret.push_back(nums[i]);
                ret.push_back(target - nums[i]);
                return ret;
            }
        }
        return ret;
    }
};

int main() {
    cout << "Hello, World!";
    vector<int> test;
    test.push_back(0);
    test.push_back(1);
    test.push_back(2);
    test.push_back(3);
    test.push_back(4);
    test.push_back(5);
    bool t = Solution().findOther(test, 0, test.size() - 1, -1);
    return 0;
}
